package practice.arraysort;

import java.util.Arrays;
import java.util.Random;

/** 冒泡排序 */
public class MaopaoSort {
    public static void main(String[] args) {
        int[] array = new int[10];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(100);
        }
        System.out.println(Arrays.toString(array));

        /*
        冒泡排序其实就是把最大值一直往最后面放
        从第1个元素开始j跟j+1相比，如果j大就交换顺序
        一直比较一轮下来后最后一个元素就是最大的了
        总共需要比较数组长度-1轮，i<长度-1，因为比到最后第一个元素肯定是最小的所以要比长度少一轮
        注意：因为每轮比完后面都已经是排序好的了大的了，而j最大只能到长度-2
             避免重复比较，所以j<长度-1-i
         */
        boolean flag;
        for (int i = 0; i < array.length-1; i++) {
            flag = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j]>array[j+1]){
                    int tem = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tem;
                    flag = true;
                }
            }
            if (!flag){
                break;
            }
            System.out.println(Arrays.toString(array));
        }
        System.out.println(Arrays.toString(array));
    }


    //冒泡排序版本2
    /*
        外层循环从最后一个下标往前，内层循环从0到外层循环下标-1,
        为了防止不必要的浪费循环，当内层一轮循环没有元素交换就跳出外层循环
     */
    private static void sort(int[] array){
        boolean flag;
        for (int j = array.length-1; j >=0; j--) {
            flag = false;
            for (int i = 0; i < j; i++) {
                if (array[i] > array[i+1]){
                    int tem = array[i];
                    array[i] = array[i+1];
                    array[i+1] = tem;
                    flag = true;
                }
            }
            if (!flag){
                break;
            }
        }
    }
}
